#ifndef __DYNAMICARRAY_H_
#define __DYNAMICARRAY_H_

#include <cstddef>
#include <cstdbool>
#include <limits.h>

//using ElementType = int;
using ElementType = void*;

class DynamicArray
{
public:
    DynamicArray();
    DynamicArray(const DynamicArray& a);
    DynamicArray& operator=(const DynamicArray& a);
    ~DynamicArray();

    void SetFreeFunc(void (*Free)(ElementType ));
    
    void SetCompareFunc(int (*Compare)(ElementType,ElementType));
    
    void SetPrintFunc(void (*Print)(ElementType));

    //插入
    //尾插法
    void InsertTail(const ElementType& element);
    //头插法
    void InsertHead(const ElementType& element);
    //中间插入
    void InsertByIndex(const ElementType& element,size_t index);

    //删除
    //按位置删除
    void RemoveByIndex(size_t index);
    //按值删除
    void RemoveByElement(const ElementType& element);

    //查找
    //按位置查找
    ElementType* FindByIndex(size_t idnex);
    //按值查找
    //返回值:下标的集合
    DynamicArray FindByElement(const ElementType& element);

    //修改
    //按位置修改
    void UpdateByIndex(size_t index,const ElementType& newValue);
    //按值修改
    void UpdateByElement(const ElementType& oldValue,const ElementType& newValue);

    ElementType& operator[](int index);  //查找和 修改统一在一个接口里面  O(1)

    //排序算法
    void Sort();
    //去重算法
    void Duplicate();
    //合并:两个有序数列合并成一个新的有序数列
    DynamicArray Merge(const DynamicArray& a);
    //取交集
    DynamicArray FindInterSection(const DynamicArray& a);
    //取并集
    DynamicArray FindUnionSection(const DynamicArray& a);
    //取补集
    DynamicArray FindDifference(const DynamicArray& a);

    //判断两个数列是否相等
    bool operator==(const DynamicArray& a);

    //二分法  没找到返回ULONG_MAX
    size_t BinarySearch(const ElementType & element);
    //判断一个数列是不是另一个数列的子数列
    bool Contains(const DynamicArray& a);
    //判断一个数列是不是连续子序列
    bool ContinueContains(const DynamicArray& a);
    //获取子序列
    DynamicArray SubSquence(size_t index,size_t len);

    void show();
private:
    //分组函数
    size_t partition(size_t start, size_t end);

    void FastSort(size_t start, size_t end,size_t CurDepth,size_t MaxDepth);
    void InsertSort(size_t start, size_t end);
    void ReSize(size_t capacity);
    ElementType *array;
    size_t capacity;
    size_t size;

    void (*Free)(void *);  //释放对象的函数指针
    int (*Compare)(void*,void*);  //比较大小的指针
    void (*Print)(void *);  //打印数据的指针
};


#endif